#ifndef __DFA_H_
#define __DFA_H_
#include <list>
#include "nfa.h"
#include "debug.h"
#include "define.h"
using namespace std;
const int N = 1e3 + 10, TOKENS = 30;
#define TOKENS 30
vector<vector<int>> dfaStateTable;
vector<int> dfaToken;

// ========= 定义集合的compare ==========
struct SetCmp
{
    const bool operator()(const set<int> &s1, const set<int> &s2) const
    {
        if (s1.size() != s2.size())
            return s1.size() < s2.size();
        SetIntIter iter1 = s1.begin(), iter2 = s2.begin();
        for (; iter1 != s1.end(); iter1++, iter2++)
        {
            if ((*iter1) != (*iter2))
                return (*iter1) < (*iter2);
        }
        return true;
    }
};
SetSet PZZ;

// ========= 定义DFA节点 ========
/*
pre: 父节点
suc: 子节点
*/
struct node
{
    int idx;              // 节点自身的id，即存在图中的位置
    int num_suc, num_pre; // 父节点、子节点数量
    int suc[TOKENS];      // 父节点、子节点位置
    list<int> pre;

    node()
    {
        num_suc = 0, num_pre = 0;
        for (register int i = 0; i < TOKENS; i++)
            suc[i] = -1;
    }

    int &operator[](int idx)
    {
        return suc[idx];
    }

    /*
    idx：   子节点编号
    token： 连接方式，反映到连接上
    */
    int link(int idx, int token)
    {
        // 连接到子节点，通过token
        this->suc[token] = idx;
        this->num_suc += 1;

        // 子节点添加父节点
        DFA[idx].pre.push_back(idx);
        DFA[idx].num_pre += 1;
    }

    /*
    删除当前节点
    意味着：
    1. 父节点滞空，子节点滞空，数量减少
    */
    int del()
    {
        // 所有子节点不再有这个父节点
        for (int i = 0; i < TOKENS; i++)
        {
            int chidx = suc[i];
            if (chidx == -1)
                continue;

            for (list<int>::iterator iter = DFA[chidx].pre.begin(); iter != DFA[chidx].pre.end(); iter++)
            {
                if ((*iter) == chidx)
                {
                    DFA[chidx].pre.erase(iter);
                    DFA[chidx].num_pre--;
                    break;
                }
            }
        }
    }

} DFA[N];

// int Dfa[N][TOKENS];     // 从1开始编号

void TranverseAndNameNfa(NFA &); // 最开始遍历，并且给NFA进行编号

// DFA构建
void BuildNaiveDFA();
void DeleteUnreachableNode();

#endif